package hashtable;

import java.util.TreeMap;

public class HashTable<K, V> {
    private final int[] capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
            805306457, 1610612741};
    public static final int upperTol = 10;
    public static final int lowerTol = 2;
//    public static final int initCapacity = 7;

    public int capacityIndex = 0;

    private TreeMap<K, V> hashtable[];
    private int M;
    private int size;

   /* public HashTable(int m) {
        this.M = m;
        size = 0;
        hashtable = new TreeMap[M];
        for (int i = 0; i < hashtable.length; i++) {
            hashtable[i] = new TreeMap<>();
        }
    }*/
   public HashTable() {
       this.M = capacity[capacityIndex];
       size = 0;
       hashtable = new TreeMap[M];
       for (int i = 0; i < hashtable.length; i++) {
           hashtable[i] = new TreeMap<>();
       }
   }
   /* public HashTable() {
        this(initCapacity);
    }*/

    /**
     * 与 的目的是为了将参数值转化为无符号的值
     * @param key
     * @return
     */
    private int hash(K key){
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize(){
        return size;
    }

     public void add(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key)){
            map.put(key, value);
        } else {
            map.put(key, value);
            size++;

            if(size >= upperTol * M && capacityIndex + 1<capacity.length){
                capacityIndex++;
                resize(capacity[capacityIndex]);
            }
        }
    }

    public void set(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key)){
            map.put(key, value);
        } else {
            throw new IllegalArgumentException("the key does not exist");
        }
    }
    public V remove(K key){
        TreeMap<K, V> map = hashtable[hash(key)];
        V ret = null;
        if(map.containsKey(key)){
            ret = map.remove(key);
            size--;
           /* if(size < lowerTol * M && M / 2 >= initCapacity){
                resize(M / 2);
            }*/
            if(size < lowerTol * M && capacityIndex - 1 >= 0){
                capacityIndex--;
                resize(capacity[capacityIndex]);
            }
        }
        return ret;
    }

    private void resize(int newM) {
        int oldM = this.M;
        this.M = newM;
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHashTable[i] = new TreeMap<>();
        }

        for (int i = 0; i < oldM; i++) {
            TreeMap<K,V> map = hashtable[i];
            for (K key: map.keySet()) {
                newHashTable[hash(key)].put(key, map.get(key));
            }
        }
        this.hashtable = newHashTable;
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }
    public V get(K key){
        return hashtable[hash(key)].get(key);
    }



}
